The present invention is directed to a method for consolidating backward resource management cells for Available Bit Rate service in an Asynchronous Transfer Mode network.
In an Asynchronous Transfer Mode (ATM) network a plurality of service categories are available, as described in xe2x80x9cThe ATM Forum Technical Committee Traffic Management Specificationxe2x80x9d, Version 4.0, af-tm-0056.000, April 1996, herein incorporated by reference. One such service is Available Bit Rate (ABR) in which the source rate, referred to as the allowed cell rate (ACR), at which the ABR source transmits data is adjusted in accordance with network congestion information feedback.
FIG. 1 shows an ABR flow control path between point-to-point end-systems (unicast) for controlling through feedback the source rate in response to changing ATM layer transfer characteristics. The point-to-point configuration includes a single sending end-system (source) 10, a single receiving end-system (destination) 20 and a network cloud 30 disposed therebetween. Network cloud 30 is an interconnection of transmission links and switching devices which provides a path for ATM traffic between the source and destination end-systems. Congestion points may exist in the network cloud and/or at the destination end-system. ABR flow control schemes are employed to control congestion at the congestion points in the network cloud and/or destination end-system which may increase queue-length, delay and/or cell loss.
In order to control the source rate, information such as bandwidth availability, state of congestion, and impending congestion of the network is conveyed to the source using Resource Management (RM) cells. In particular, RM cells include an Explicit Rate (ER) field that carries a 16-bit floating-point number representing the explicit rate, a Congestion Indication (CI) bit, which is used to signal a source to increase/decrease its rate by some predefined amount, and a No-Increase (NI) bit to signal a source to maintain its current rate.
Initially, source 10 generates Forward Resource Management (FRM) cells which are transmitted along with data cells via the network cloud 30 towards the destination 20. Backward Resource Management (BRM) cells are generated via looping back an FRM cell at the destination end-system and/or are directly created by various congestion points, e.g., ATM switches, in the network cloud. The BRM cells carry feedback information provided by the destination end-system as well as by other congestion points in the network cloud back to the source 10 which, in turn, adjusts its source rate based on the congestion information in the BRM cells. RM cells are marked with switch congestion information such as the ER field and CI and NI bits as they are transmitted in a forward direction (from the source toward the destination) or in a reverse direction (from the destination back toward the source).
End-systems may also be arranged in a more complex point-to-multipoint tree (multicast tree) including a source end-system (root) connected by branches to a plurality of destination end-systems (leaves) and at least one branch point disposed between the root and the leaves. Specifically, a branch is defined as any point-to-point segment of the point-to-multi-point tree and a branch point is an intersection of two or more branches. By way of example, a multicast tree having a root 40, a branch point 60, two leaves 80, 100 and network clouds 50, 70, 90 is shown in FIG. 2. Each network cloud 50, 70, 90 comprises an interconnection of transmission links and switching devices which provide the path between the root (source end-system) or branch point and another branch point or a leaf (destination end-system). Congestion points may exist in the network cloud and/or at the leaf (destination end-system). The multicast tree shown in FIG. 2 is for illustrative purposes only and is not intended to limit the number of branches, branch points, leaves or arrangement thereof. FRM cells and data cells received by branch point 60 from the root 40 are replicated (multicast) along each branch downstream in the forward flow direction toward the leaves 80, 100. BRM cells are generated via looping back an FRM cell at the leaf (destination end-system) and/or are directly created by various congestion points, e.g., ATM switches, in the network clouds. BRM cells returning from the leaves and/or the congestion points to the root are consolidated at branch point 60 before being passed back upstream to the root 40. Consolidation of the BRM cells at the branch point prevents BRM cell implosion on the root and maintains the same number of BRM cells returning to the root irrespective of the number of leaves in the tree. In short, branch point 70 replicates the RM cells traveling in a forward direction and consolidates the RM cells traveling in a reverse direction to ensure that cell flows on each branch of the point-to-multipoint tree maintain the same conformance definitions as point-to-point cell flows.
As each copy of the FRM cell travels from the root to the plural leaves in a point-to-multipoint tree, its respective ER field, CI bit and NI bit is marked to convey information regarding the degree of congestion/bandwidth availability of traversed congested points. The congestion information in the ER field, Cl bit and NI bit of the RM cell are continuously updated as the cell travels in the forward/reverse flow directions.
As discussed above, in a point-to-multipoint tree the number of BRM cells which reach a particular branch point must be consolidated in order to limit the bandwidth consumed by BRM cells of each multicast branch and ensure that the volume of RM cells for an ABR end-point does not increase with the number of leaves of the multicast tree. On average over an extended period for every FRM cell that reaches a branch point at most one BRM cell is returned or passed back through the branch point towards the root (source end-system).
One conventional solution for performing BRM cell consolidation will be referred to as the xe2x80x9cBranch point generation of BRMxe2x80x9d. In this approach congestion information memory devices are associated with each forward ABR multicast VC at a branch point for storing the ER, CI, NI congestion information. When a BRM cell returns from a branch, the congestion/bandwidth availability information, e.g. ER field, CI bit, and NI bit, of the BRM cell of the current cell is consolidated with the previously stored values in the respective local congestion information memory devices, the updated information is stored in the local congestion information memory devices and the BRM cell is discarded. In a preferred embodiment the ER, CI, NI congestion information memory devices store the result of the min(previous ER, incoming ER), the CI bit of the incoming BRM cell ORed with the previously stored CI bit, and the NI bit of the incoming BRM cell ORed with the previously stored NI bit, respectively. When an FRM cell arrives at a branch point it is multicast downstream along each of the branches of the branch point. In addition, arrival of the FRM cell at the branch point triggers generation of a BRM cell which is sent to the source. Before the generated BRM cell is sent to the source it xe2x80x9cpicks upxe2x80x9d the congestion information stored in the congestion information memory devices. The BRM cell xe2x80x9cpicks-upxe2x80x9d the consolidated congestion/bandwidth availability information by storing in the BRM cell the result of the min(ER stored in congestion information memory devices, ER of the BRM cell), the CI bit stored in congestion information memory devices ORed with the CI bit of the BRM cell, the NI bit stored in the congestion information memory devices ORed with the NI bit of the BRM cell. This approach is disadvantageous in that it requires the switch to generate a large number of BRM cells.
Another well-known conventional scheme for performing BRM cell consolidation is referred to as the xe2x80x9cready-bitxe2x80x9d approach. In this approach, for each forward multicast ABR Virtual Channel (VC) passing through a branch point there are a plurality of associated congestion information memory devices such as local registers for consolidating congestion information of all of the destinations along with an additional one-bit memory for storing a xe2x80x9cready-bitxe2x80x9d. The congestion information memory devices store the congestion network feedback information from the RM cells such as the ER field, CI bit and NI bit. Initially the ready-bit is set to xe2x80x9c0xe2x80x9d and the congestion information memory devices are reset, that is, the CI and NI bits stored in the congestion information memory devices are set to xe2x80x9c0xe2x80x9d and the ER register is set to infinity or the maximum link capacity. When a FRM cell arrives at a branch point, the ready-bit for the corresponding forward VC is set to xe2x80x9c1xe2x80x9d. In the reverse direction when a BRM cell arrives at the branch point if the ready-bit is xe2x80x9c0xe2x80x9d, then the congestion/bandwidth availability information, e.g. ER field, CI bit, and NI bit, of the BRM cell of the current cell is consolidated with the previously stored values, the updated information is stored in the congestion information memory devices and the BRM cell is discarded. In a preferred embodiment the congestion information memory devices store the result of the min(previous ER, incoming ER), the CI bit of the incoming BRM cell ORed with the previously stored CI bit, and the NI bit of the incoming BRM cell ORed with the previously stored NI bit, respectively. Otherwise, if the ready-bit is xe2x80x9c1xe2x80x9d when the BRM cell arrives at a branch point then the BRM cell will xe2x80x9cpick-upxe2x80x9d the consolidated congestion/bandwidth availability information from the congestion information memory devices and consolidate the stored ER, CI, NI information. The BRM cell xe2x80x9cpicks-upxe2x80x9d the consolidated congestion/bandwidth availability information by performing the min(), OR, OR operations described above for ER, CI and NI, respectively. Thereafter, the congestion information memory devices are reset, that is, the CI and NI bits stored in the congestion information memory devices are set to xe2x80x9c0xe2x80x9d and the ER value stored in the congestion information memory devices is set to infinity or the maximum link capacity. The BRM cell with the updated congestion information is then passed back to the root (source end-system).
This conventional scheme is disadvantageous for several reasons. Poor transient queue-length is attained, especially during start-up because feedback is dominated by the first BRM cell to arrive at the branch point after a FRM has been sent. Consequently, queue and cell loss will quickly occur at various congestion points in the network cloud along the path from the source to the destination upon receipt of BRM cells from relatively fast close leaves. In addition, the ready-bit approach results in relatively high consolidation noise since a BRM cell may be passed back to the root without waiting for arrival at the branch point of the congestion feedback information from the most congested branch.
In order to prevent the occurrence of consolidation noise the ready-bit approach may be modified in a xe2x80x9cwait-for-allxe2x80x9d scheme wherein for each FRM cell, at least one BRM cell from every branch must be received at a branch point before passing a BRM cell back to the root. Specifically, when a BRM cell returns, the branch point determines whether a BRM cell has been received from every branch. If a BRM cell has not been received from every branch then the congestion information of the BRM cell is consolidated into the congestion information memory devices and the BRM cell is discarded. When a BRM cell has been received from every branch then the congestion information from the congestion information memory devices is consolidated in the BRM cell, the congestion information memory devices are reset, that is, the CI and NI bits stored in the congestion information memory devices are set to xe2x80x9c0xe2x80x9d and the ER register is set to infinity or the maximum link capacity, and the BRM cell containing the updated congestion information is passed back to the root (source end-system).
This alternative approach, however, requires a one-bit memory per actual branch for each forward VC to record arrivals of BRM cells in a current cycle. Under practical implementation, a static data structure is used to organize such one-bit memories. The overall memory capacity must therefore be based on the worst-case scenario, e.g. Mmax*Nmax bits at each branching point, where Mmax is the maximum number of branches (fanout) allowed for a forward VC and Nmax is the maximum number of forward VCs allowed at a branching point. Since Mmax and Nmax are worst-case values, instead of the actual number of branches M and active forward VCs N, respectively, they are quite large and, thus, may require a significant amount of memory.
Additional disadvantages associated with this alternative xe2x80x9cwait-for-allxe2x80x9d scheme is that the branch point is forced to wait for a return BRM cell from every branch thereby slowing down the overall response time. For example, the BRM cell of a bottleneck branch having a corresponding minimum ER value among all branches may arrive at the branching point long before the remaining non-bottleneck branch return BRM cells are received. Even more problematic is that control of the ABR source flow for the entire multicast VCs may cease as a result of a single non-responsive branch, that is, a branch which has not returned a BRM cell.
The transient response time using the wait-for-all BRM consolidation technique may be improved by using Fast Pass Back (FPB). In FPB the ER of the previous pass back BRM cell is stored at a branch point. The ER of each incoming return BRM cell is compared with the ER of the previous pass back BRM cell. If the ER of the incoming return BRM cell is substantially less than the ER of the previous pass back BRM cell then the incoming return BRM cell is passed back immediately without waiting for receipt of the return BRM cells of the remaining branches. The FPB modification of the wait-for-all approach, however, is disadvantageous in that the BRM cell pass back rate may exceed the FRM cell rate at the branch point.
Thus, two competing goals must be balanced, namely waiting for the branch having the minimum ER value in its BRM cell without having to wait for receipt of return BRM cells from every branch. On the one hand, if the branch point waits for receipt of only a few return BRM cells then BRM cells having a non-minimum ER value may be passed back to the root before receipt of the minimum ER carrying BRM cell thereby increasing the queue-length and cell loss. On the other hand, forcing a branch point to wait for receipt of return BRM cells from most of the branches may be disadvantageous for several reasons. If the current ER is greater than the previous pass back ER value, loss of utilization may result. Conversely, if the current ER value is less than the previous pass back ER value, queue-length and cell loss may increase due to unnecessary delay in forcing the root (source end-system) to wait for irrelevant branches. It is therefore desirable to develop a BRM consolidation method that solves the aforementioned problems associated with conventional schemes.
The present invention is directed to a method for consolidating backward resource management cells in an available bit rate point-to-multipoint tree including a root, a plurality of leaves and a branch point interconnected between the root and the leaves. Initially the congestion information memory devices which store congestion information from the backward resource management cells are reset. For each incoming return backward resource management cell to the branch point a determination is made whether the branch point has received a return backward resource management cell from a predetermined number of candidates in a candidate set of candidate-branches. If the branch point has received a return backward resource management cell from the predetermined number of candidates in the candidate set then the consolidated congestion information from the incoming return backward resource management cell and congestion information in the congestion information memory devices is stored in the incoming return backward resource management cell which is passed back to the root. Otherwise, if the branch point has not received a return backward resource management cell from the predetermined number of candidates in the candidate set then the consolidated congestion information from the incoming return backward resource management cell and the congestion information in the congestion information memory devices are stored in the congestion information memory devices and the incoming return backward resource management cell is discarded.
In addition, the invention relates to a method for controlling a rate of pass back of incoming return backward resource management cells at a branch point to a source for available bit rate service in an asynchronous transfer mode network. A token is generated by a token generator for each forward resource management cell that arrives at the branch point and is stored in a token bucket. For each incoming backward resource management cell that arrives at the branch point a determination is made whether a token is available in the token bucket. If a token is not available then the congestion information in the incoming backward resource management cell is consolidated in the congestion information memory devices and the incoming backward resource management cell is then discarded. Otherwise, the consolidated congestion information from the incoming return backward resource management cell and congestion information in the congestion information memory devices is stored in the incoming return backward resource management cell which is then passed back to the root and a token is removed from the token bucket.
Furthermore, the invention is directed to a method for consolidating backward resource management cells at a branch point root for available bit rate service in an asynchronous transfer mode network. For each incoming return backward resource management cell a determination is made whether criteria for pass back of the incoming return backward resource management cell is satisfied. If the criteria for pass back of the incoming return backward resource management cell is satisfied then the incoming return backward resource management cell is passed back. Otherwise, a ratio of an incoming explicit rate of an incoming return backward resource management cell to a historical explicit rate of previous return backward resource management cells is calculated and a fast pass back probability value corresponding to the calculated ratio is determined based on a dynamically adjusted non-decreasing fast pass back probability function. Then a random number is generated and a determination is made whether the randomly generated number is less than or equal to the fast pass back probability value. If the randomly generated number is less than or equal to the fast pass back probability value then the incoming return backward resource management cell congestion information from the incoming return backward resource management cell is consolidated with the congestion information stored in the congestion memory devices and the consolidated incoming return backward resource management cell is passed back to the root. Otherwise, if the random number is greater than the fast pass back probability value then in the congestion information memory devices the congestion information from the incoming return backward resource management cells is consolidated with the congestion information stored in the congestion information memory devices and the incoming return backward resource management cell is discarded.
Other objects and features of the present invention will become apparent from the following detailed description considered in conjunction with the accompanying drawings. It is to be understood, however, that the drawings are intended solely for purposes of illustration and not as a definition of the limits of the invention, for which reference should be made to the appended claims.